package book;

import java.util.Stack;

public class MultiSegmentGraphSolution {
    // 定义最大路径权值。若顶点间路径权值过大，认为两个顶点没有边连接。
    static final int MAX = 1000000;
    
    // 求多段图的最短路径
    void solve(DirectedWeightGraph dwg) {
        int n = dwg.V; // 图的顶点总数

        int[] cost = new int[n]; // cost数组记录最短路径长度
        int[] path = new int[n]; // path数组记录最短路径的上一节点位置

        // 初始化cost数组与path数组
        for (int i = 0; i < n; i++) {
            cost[i] = dwg.edges[0][i];
            path[i] = -1;
        }
        // 初始化源点状态
        cost[0] = 0;
        path[0] = 0;

        // 从j=1开始，考察从源点0到顶点j的所有入边
        for (int j = 1; j < n; j++) {
            int min = MAX;
            for (int i = 0; i < j; i++) {
                // 没有边连接, 跳过
                if (dwg.edges[i][j] >= MAX)  continue;
                
                // 有边连接，更新cost[j]、path[j]
                if (cost[i] + dwg.edges[i][j] <= min) {
                    cost[j] = cost[i] + dwg.edges[i][j];
                    min = cost[j];
                    path[j] = i;
                }
            }
        }

        // 使用栈还原path并输出
        Stack<Integer> pathStk = new Stack<>();
        int i = n - 1; 
        while (i != 0) {
            pathStk.push(i);
            i = path[i];
        }
        System.out.print("最短路径: 0"); // 源点
        while (!pathStk.empty()) 
            System.out.print(" -> " + pathStk.pop());
        System.out.println(); 

        // 输出最短路径长度
        System.out.println("最短路径长度: " + cost[n - 1]);
    }

    // 测试运行：创建有向加权图并计算最短路径
    void test() {
        int n = 10; // 顶点个数为10
        
        // 创建顶点个数为10的有向加权图
        DirectedWeightGraph dwg = new DirectedWeightGraph(n);

        // 图初始化：输入所有的路径
        dwg.addEdge(0, 1, 4);
        dwg.addEdge(0, 2, 2);
        dwg.addEdge(0, 3, 3);
        dwg.addEdge(1, 4, 9);
        dwg.addEdge(1, 5, 8);
        dwg.addEdge(2, 4, 6);
        dwg.addEdge(2, 5, 7);
        dwg.addEdge(2, 6, 8);
        dwg.addEdge(3, 5, 4);
        dwg.addEdge(3, 6, 7);
        dwg.addEdge(4, 7, 5);
        dwg.addEdge(4, 8, 6);
        dwg.addEdge(5, 7, 8);
        dwg.addEdge(5, 8, 6);
        dwg.addEdge(6, 7, 6);
        dwg.addEdge(6, 8, 5);
        dwg.addEdge(7, 9, 7);
        dwg.addEdge(8, 9, 3);
        
        // 调用核心方法求解最短路径
        solve(dwg);
    }

    public static void main(String args[]) {
        new MultiSegmentGraphSolution().test();
    }
}
